package com.pan.alg.leecode;

import java.util.Random;

public class QuickSort {
    
    public static int[] quickSort(int[] arr){
        
        int length = arr.length;
        doQuickSort(arr,0,length-1);
        
        return arr;
    }

    private static void doQuickSort(int[] arr, int l, int r) {

        if(r<=l){
            return;
        }

        int index = partition(arr,l,r);
        doQuickSort(arr,l,index-1);
        doQuickSort(arr,index+1,r);
    }

    /**
     * 对arr【l...r】部分进行partion操作
     * 返回index，使得arr【l...index-1】<arr[index],arr[index+1,r]>arr[index]
     *
     * @param arr
     * @param l
     * @param r
     * @return
     */
    private static int partition(int[] arr, int l, int r) {
        //取左边第一个作为标准
        int flag = arr[l];
        int j=l;
        //arr[l+1...j]<v arr[j+i...r]>v
        for (int i = l+1; i <= r; i++) {
            if(flag>arr[i]){
                swap(arr,j+1,i);
                j++;
            }
        }
        swap(arr,l,j);
        return j;
    }

    private static void swap(int[] arr,int i, int i1) {
        int tmp = arr[i];
        arr[i]=arr[i1];
        arr[i1]=tmp;
    }


    // 冒泡排序，a表示数组，n表示数组大小
    public void bubbleSort(int[] a, int n) {
        if (n <= 1) {
            return;
        }

        for (int i = 0; i < n; ++i) {
            // 提前退出冒泡循环的标志位
            boolean flag = false;
            for (int j = 0; j < n - i - 1; ++j) {
                if (a[j] > a[j+1]) { // 交换
                    int tmp = a[j];
                    a[j] = a[j+1];
                    a[j+1] = tmp;
                    flag = true;  // 表示有数据交换
                }
            }
            if (!flag) {
                break;  // 没有数据交换，提前退出
            }
        }
    }
}
